package com.fr.lintcode;

public class Q1691 {

	/**
	 * 1691. 买卖股票的最佳时机 V 
	 * 给出一个股票n天的价格，每天最多只能进行一次交易，可以选择买入一支股票或卖出一支股票或放弃交易，输出能够达到的最大利润值
	 * 
	 * 样例 样例 1:
	 * 
	 * 给出 `a = [1,2,10,9]`, 返回 `16` 输入: [1,2,10,9] 输出: 16
	 * 
	 * 解释: 你可以在第一天和第二天买入股票，第三天和第四天卖出 利润：-1-2+10+9 = 16 样例 2:
	 * 
	 * 给出 `a = [9,5,9,10,5]`, 返回 `5` 输入: [9,5,9,10,5] 输出: 5
	 * 
	 * 解释: 你可以在第2天买入，第4天卖出 利润:-5 + 10 = 5 注意事项 1 \leq n \leq 100001≤n≤10000
	 * 
	 * @param a: the array a
	 * @return: return the maximum profit
	 */
	//dp
	public int getAns(int[] a) {
		// write your code here
		if(a == null) {
			return 0;
		}
		int length = a.length;
		int [] used = new int[length];
		int index = findMaxUnused(a, used);
		while(index > 0) {
			int t = findMinUnusedbefore(a, used, index);
			if (t >= 0) {
				used[index] = 1;
				used[t] = -1;
			}else {
				used[index] = 2;
			}
		}
		int count = 0;
		for(int i = 0; i < length ; i ++) {
			if(used[i] == -1) {
				count = count - a[i];
			}else if(used[i] == 1) {
				count = count - a[i];
			}
		}
		return count;
	}

	private int findMinUnusedbefore(int[] a, int[] used, int index) {
		Integer min = null;
		int index1 = -1;
		for(int i = 0; i < index; i ++) {
			if(used[i] == 0 || used[i] == 2) {
				if(min == null || min > a[i]) {
					min = a[i];
					index1 = i;
				}
			}
		}
		return index1;
	}

	private int findMaxUnused(int[] a, int[] used) {
		Integer max = null;
		int index = -1;
		for(int i = 1; i < a.length; i ++) {
			if(used[i] == 0) {
				if(max == null || max < a[i]) {
					max = a[i];
					index = i;
				}
			}
		}
		return index;
	}

}
